/**
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 *
 * 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 *
 * 链接：https://leetcode.cn/problems/triangle
 * 思路：动态规划
 */
class MinimumTotal {
    /**
     * 法一：
     * 方法：动态规划（从上往下找状态）
     * 状态：
     *
     *  子状态：从(0,0)到(1,0),(1,1),(2,0),...(n,n)的最短路径和
     *
     *  F(i,j): 从(0,0)到(i,j)的最短路径和
     * 状态递推：
     *
     *  F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]
     *
     * 初始值：
     *
     *  F(0,0) = triangle[0][0]
     *
     * 返回结果：
     *
     *  min(F(n-1, i))
     */
//    public int minimumTotal(List<List<Integer>> triangle) {
//        int row=triangle.size();
//        int[][] dp=new int[row][row];
//        dp[0][0]=triangle.get(0).get(0);
//        for(int i=1;i<row;i++) {
//            for(int j=0;j<=i;j++) {
//                if(j==0) {//处理左边界
//                    dp[i][j]=dp[i-1][0]+triangle.get(i).get(0);
//                } else if(i==j) {//处理右边界
//                   dp[i][j]=dp[i-1][j-1]+triangle.get(i).get(i);
//                } else {//状态方程: dp[i][j]=Math.min(dp[i-1][j-1],dp[i-1][j])+triangle.get(i).get(j);
//                    dp[i][j]=Math.min(dp[i-1][j-1],dp[i-1][j])+triangle.get(i).get(j);
//                }
//            }
//        }
//        int min=dp[row-1][0];
//        for(int i=1;i<row;i++) {
//            min=Math.min(min,dp[row-1][i]);
//        }
//        return min;
//    }

    /**
     * 法二：动态规划（自底向上）
     * 方法二：动态规划（反向思维）
     * 状态：
     *
     *  子状态：从(n,n),(n,n-1),...(1,0),(1,1),(0,0)到最后一行的最短路径和
     *
     *  F(i,j): 从(i,j)到最后一行的最短路径和
     * 状态递推：
     *
     *  F(i,j) = min( F(i+1, j), F(i+1, j+1)) + triangle[i][j]
     *
     * 初始值：
     *
     *  F(n-1,0) = triangle[n-1][0], F(n-1,1) = triangle[n-1][1],..., F(n-1,n-1) = triangle[n-1]
     * [n-1]
     *
     * 返回结果：
     *
     *  F(0, 0)
     *
     *
     *
     * 这种逆向思维不需要考虑边界，也不需要最后寻找最小值，直接返回F(0,0)即可
     *
     *
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int row=triangle.size();
        int[][] dp=new int[row][row];
        for(int i=0;i<row;i++) {
            dp[row-1][i]=triangle.get(row-1).get(i);
        }
        for(int i=row-2;i>=0;i--) {
            for(int j=0;j<=i;j++) {
                dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}